// 1192. [简洁塔杨DFS/连通分量] 查找集群内的关键连接
// https://leetcode.cn/problems/critical-connections-in-a-network/
// Tarjan算法是用来求有向图的强连通分量的,求双连通分量的Tarjan算法,【Tarjan算法是基于对图深度优先搜索的】
// 每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，
// 回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
// 力扣数据中心有 n 台服务器，分别按从 0 到 n-1
// 的方式进行了编号。它们之间以「服务器到服务器」
// 点对点的形式相互连接组成了一个内部集群，其中连接 connections
// 是无向的。从形式上讲， connections[i] = [a, b] 表示服务器 a 和 b
// 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。
// 关键连接是在该集群中的重要连接，假如我们将它移除，便会导致某些服务器无法访问其他服务器。
// 请你以任意顺序返回该集群内的所有 「关键连接」。
// 输入：n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
// 输出：[[1,3]]
// 解释：[[3,1]] 也是正确的。
// 输入：n = 2, connections = [[0,1]]
// 输出：[[0,1]]

#include <bits/stdc++.h>
using namespace std;

#define PF(...) printf(__VA_ARGS__)
#define FRE(x) freopen("d:/oj/" #x ".in", "r", stdin)

// dfn[i]表示第i个点被搜索到的次序编号
// low[i]表示以i为根的子树下的最小的时间编号 若dfn[i]==low[i]
// 即该点为一个强连通分量子树的根

class Solution {
 private:
  int nSeq = 0;
  vector<int> dfn, low;  // 节点的时间戳和追溯值
  vector<vector<int>> res;
  vector<vector<int>> adj;  // 邻接表 adj[i][j] = v表示i连接j

  // 节点u -> 节点v
  void tarjan(int u, int preNode) {  // preNode 为 u 的前节点
    dfn[u] = low[u] = ++nSeq;
    for (int v : adj[u]) {
      if (v == preNode) continue;
      if (!dfn[v]) {
        tarjan(v, u);
        low[u] = min(low[u], low[v]);
        if (dfn[u] < low[v]) {
          res.push_back({u, v});
        }
      } else {
        low[u] = min(low[u], dfn[v]);
      }
    }
  }

 public:
  vector<vector<int>> criticalConnections(size_t nodeCnt,
                                          vector<vector<int>>& connections) {
    dfn.resize(nodeCnt);  // 初始化一下工具人数组们
    low.resize(nodeCnt);
    adj.resize(nodeCnt);
    for (auto edge : connections) {  // 邻接表存图
      adj[edge[0]].push_back(edge[1]);
      adj[edge[1]].push_back(edge[0]);
    }
    // Tarjan 更新以 u 为根的搜索树。-1 表示根节点无父节点
    for (int u = 0; u < nodeCnt; u++) {
      if (!dfn[u]) {
        tarjan(u, -1);
      }
    }
    return res;
  }
};

// int main()
//{
//    Solution sol;
//    auto vtOut = sol.findRedundantConnection({});
//    for (auto n : vtOut) PF("%d,",n); PF("\n");
//    return 0;
//}
